import qualified Data.Set as Set

splitAll :: Eq a => [a] -> [a] -> [[a]]
splitAll _ [] = []
splitAll delims xs = 
    token : splitAll delims rest
    where
        isDelimiter = (`elem` delims)
        token       = takeWhile (not . isDelimiter) xs
        rest        = dropWhile isDelimiter $ dropWhile (not . isDelimiter) xs

type Card = Int
type Deck = [Card]
type GameState = (Deck, Deck)
type Record = Set.Set String

parseInput :: String -> GameState
parseInput str = (deck1, deck2)
    where
        tokens = splitAll [""] $ lines str

        deck1 = map read . tail $ tokens !! 0
        deck2 = map read . tail $ tokens !! 1

isStartSubGame :: GameState -> Bool
isStartSubGame (deck1, deck2) = deck1Pass && deck2Pass
    where
        deck1Pass = (head deck1) <= (length . tail $ deck1)
        deck2Pass = (head deck2) <= (length . tail $ deck2)

rounding :: GameState -> GameState
rounding state@(deck1, deck2) = 
    if play1Win
        then (rest1 ++ [head1,head2], rest2)
        else (rest1, rest2 ++ [head2,head1])
    where
        play1Win
            | isStartSubGame state = fst . play $ subGameState
            | otherwise = head1 > head2

        subGameState = (take head1 rest1, take head2 rest2)

        head1 = head deck1
        head2 = head deck2

        rest1 = tail deck1
        rest2 = tail deck2

play :: GameState -> (Bool, Deck)
play state = doPlay Set.empty state
    where
        doPlay :: Record -> GameState -> (Bool, Deck)
        doPlay record state@(deck1, deck2)
            | null deck1 = (False, deck2)
            | null deck2 = (True,  deck1)
            | Set.member stateStr record = (True, deck1)
            | otherwise = doPlay newRecord $ rounding state
            where
                stateStr = show deck1 ++ show deck2
                newRecord = Set.insert stateStr record

score :: Deck -> Card
score = sum . zipWith (*) [1..] . reverse

main :: IO ()
main = do
    input <- readFile "input.txt"
    print . score . snd . play . parseInput $ input

    